package Sort;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/5/13
 * \* Time: 15:40
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class Bubble {

    public static void sort(int []arr){
        for (int i = 0;i<arr.length;i++){
            for(int j = 0;j<arr.length-i-1;j++){
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] =tmp;
                }
            }
        }
    }

    public static void sort1(int []arr){
        for (int i =0;i<arr.length ; i++){
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }

    //插入排序
    public static void sort2(int[]arr){

        for (int i = 1;i<arr.length;i++){
            int tmp = arr[i];
            int j = i - 1;
            for(; j >= 0;j--){
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    //希尔排序
    public static void sort3(int[]arr,int gap){
        for(int i = 1;i<arr.length;i++){
            int tmp = arr[i];
            int j = i - gap;
            for(;j>=0;j-=gap){
                if(arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void shell(int[]arr){
        int[]drr={5,3,1};
        for(int i =0;i<drr.length;i++){
            sort3(arr,drr[i]);
        }
    }


    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    public static void mergeSortInternal(int[]arr,int low,int high){
        if(low >= high){
            return;
        }
        int mid = low + ((high - low) >>>1);
        //左边递归
        mergeSortInternal(arr,low,mid);
        //右边递归
        mergeSortInternal(arr,mid+1,high);

        //合并两边数组
        merge(arr,low,mid,high);
    }

    public static void merge(int[]arr,int low,int mid,int high){
        int [] tmp = new int[high - low + 1];
        int k =0;
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;
        while (s1 <= e1 && s2 <= e2){
            if(arr[s1] < arr[s2]){
                tmp[k] = arr[s1];
                k++;
                s1++;
            }else {
                tmp[k] = arr[s2];
                k++;
                s2++;
            }
        }
        while (s1 <= e1){
            tmp[k] = arr[s1];
            k++;
            s1++;
        }
        while ((s2 <= e2)){
            tmp[k] = arr[s2];
            k++;
            s2++;
        }

        for(int i =0;i<arr.length;i++){
            tmp[i+low] = arr[i];

        }
    }


    //快排
    public static void sort5(int[] arr,int start,int end){
        if(start >= end)  return;
        int left = start;
        int right = end;
        int tmp = arr[left];
        while (left < right){
            while (left < right && arr[right] >= tmp){
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        sort5(arr,start,left);
        sort5(arr,left+1,end);
    }

    public static int findMaxGap(int[] A, int n) {
        // write code here
        int max1 = 0;
        for(int i = 0; i < A.length;i++){
            int max = i;
            for(int j = i + 1; j <A.length;j++){
                if(A[j] < A[max]){
                    max = j;
                }
            }
            int tmp = A[i];
            A[i] = A[max];
            A[max] = tmp;
            max1 = A[max];
        }
        return max1 - Math.min(A[0],A[n-1]);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[] { 2,7,3,1,1 };
        int[] nums2 = new int[] { 2,7,3,1,1 };
        int[] arr = new int[nums1.length];
        for(int i = 0 ; i < nums1.length;i++){
            for(int j = 0 ; j <nums2.length;i++){
                if(nums1[i] == nums2[j]){
                    arr[i] = nums1[i];
                    break;
                }
            }
        }
        for(int num : arr){
            System.out.println(num);
        }
        //sort5(nums, 0, nums.length - 1);
//        int max = findMaxGap(nums,nums.length);
//        System.out.println(max);


    }


}
